import random
import math

def assign_cluster(x, c):
    min_distance = float("inf") #初始化最小距离
    cluster_index = 0
    for i, center in enumerate(c):
        #计算欧氏距离
        distance = math.sqrt(sum((xi - ci) ** 2 for xi, ci in zip(x, center)))  
        if distance < min_distance:
            min_distance = distance
            cluster_index = i
    return cluster_index


def Kmeans(data, k, epsilon=1e-4, max_iterations=100):
    #随机选择中心
    centers = random.sample(data, k)
    #初始化聚类结果
    for _ in range(max_iterations):
        clusters = [[] for _ in range(k)]
        labels = []
        for point in data:
            cluster_idx = assign_cluster(point, centers)
            clusters[cluster_idx].append(point)
            labels.append(cluster_idx)
    #更新中心点
        new_centers = []
        for cluster in clusters:
            if not cluster:
                new_centers.append(random.choice(data))  
            else:
                new_center = [sum(dim) / len(cluster) for dim in zip(*cluster)]
                new_centers.append(new_center)
    #检查中心点变化是否小于阈值
        center_shift = sum(
            math.sqrt(sum((ci - nci) ** 2 for ci, nci in zip(center, new_center)))  
            for center, new_center in zip(centers, new_centers)
        )
        if center_shift < epsilon:
            break
        centers = new_centers

    return centers, labels

if __name__ == "__main__":
    # 生成3类随机数据点
    centers = [[1, 1], [4, 4], [7, 7]]
    data = []
    for center in centers:
        for _ in range(100):
            data.append([random.gauss(center[0], 0.5), random.gauss(center[1], 0.5)])

    # 运行K-Means算法
    k = 3
    final_centers, labels = Kmeans(data, k)

    # 输出结果
    print("最终聚类中心：")
    for i, center in enumerate(final_centers):
        print(f"簇{i}: {center}")

    # 可视化
    import matplotlib.pyplot as plt
    colors = ['r', 'g', 'b']
    for i, point in enumerate(data):
        plt.scatter(point[0], point[1], c=colors[labels[i]])
    for center in final_centers:
        plt.scatter(center[0], center[1], c='black', marker='x', s=100)
    plt.title("K-Means")
    plt.show()
